{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Subarrays With More Ones Than Zeros"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #binary-search #divide-and-conquer #ordered-set #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #二分查找 #分治 #有序集合 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subarraysWithMoreZerosThanOnes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #1 比 0 多的子数组个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个只包含 <code>0</code> 和 <code>1</code> 的数组 <code>nums</code>，请返回 <code>1</code> 的数量 <strong>大于 </strong><code>0</code> 的数量的子数组的个数。由于答案可能很大，请返回答案对&nbsp;<code>10<sup>9</sup>&nbsp;+ 7</code>&nbsp;<strong>取余</strong>&nbsp;的结果。</p>\n",
    "\n",
    "<p>一个 <strong>子数组</strong> 指的是原数组中连续的一个子序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> nums = [0,1,1,0,1]\n",
    "<strong>输出:</strong> 9\n",
    "<strong>解释:</strong>\n",
    "长度为 1 的、1 的数量大于 0 的数量的子数组有: [1], [1], [1]\n",
    "长度为 2 的、1 的数量大于 0 的数量的子数组有: [1,1]\n",
    "长度为 3 的、1 的数量大于 0 的数量的子数组有: [0,1,1], [1,1,0], [1,0,1]\n",
    "长度为 4 的、1 的数量大于 0 的数量的子数组有: [1,1,0,1]\n",
    "长度为 5 的、1 的数量大于 0 的数量的子数组有: [0,1,1,0,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> nums = [0]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong>\n",
    "没有子数组的 1 的数量大于 0 的数量。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> nums = [1]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong>\n",
    "长度为 1 的、1 的数量大于 0 的数量的子数组有: [1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-subarrays-with-more-ones-than-zeros](https://leetcode.cn/problems/count-subarrays-with-more-ones-than-zeros/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-subarrays-with-more-ones-than-zeros](https://leetcode.cn/problems/count-subarrays-with-more-ones-than-zeros/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,1,0,1]', '[0]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList \n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        sl=SortedList()\n",
    "        s=0\n",
    "        res=0\n",
    "        sl.add(s)\n",
    "        for i in nums:\n",
    "            if i==0:s-=1\n",
    "            else:s+=1\n",
    "            res+=sl.bisect_left(s)\n",
    "            sl.add(s)\n",
    "        return res%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        sd1 = SortedList()\n",
    "        cache = 0\n",
    "        ans = 0\n",
    "        sd1.add(0)\n",
    "        for k,v in enumerate(nums):\n",
    "            if v == 0:\n",
    "                cache -= 1\n",
    "            else:\n",
    "                cache += 1\n",
    "            ans += sd1.bisect_left(cache)\n",
    "            ans %= 10 ** 9 + 7\n",
    "            sd1.add(cache)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1 <= nums.length <= 105\n",
    "# 即：统计和为正数的子数组有多少个\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        preSum = [0]\n",
    "        for num in nums:\n",
    "            preSum.append(preSum[-1] + (1 if num == 1 else -1))\n",
    "\n",
    "        res = 0\n",
    "        lis = SortedList()\n",
    "        for s in preSum:\n",
    "            index = lis.bisect_left(s)\n",
    "            res += index\n",
    "            lis.add(s)\n",
    "\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        #把0改成-1,把问题转化成求子数组和大于0的个数\n",
    "        pre=[0]\n",
    "        for v in nums:\n",
    "            if not v:\n",
    "                v-=1\n",
    "            pre.append(pre[-1]+v)\n",
    "        check=SortedList()\n",
    "        ans=0\n",
    "        for num in pre:\n",
    "            ans+=check.bisect_left(num)\n",
    "            check.add(num)\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1 <= nums.length <= 105\n",
    "# 即：统计和为正数的子数组有多少个\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        preSum = [0]\n",
    "        for num in nums:\n",
    "            preSum.append(preSum[-1] + (1 if num == 1 else -1))\n",
    "\n",
    "        res = 0\n",
    "        lis = SortedList()\n",
    "        for s in preSum:\n",
    "            index = lis.bisect_left(s)\n",
    "            res += index\n",
    "            lis.add(s)\n",
    "\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "\n",
    "        pref = [0]\n",
    "        for num in nums:\n",
    "            if num:\n",
    "                pref.append(1)\n",
    "            else:\n",
    "                pref.append(-1)\n",
    "            pref[-1]+=pref[-2]\n",
    "\n",
    "        ans = 0\n",
    "        lst = SortedList()\n",
    "        for num in pref:\n",
    "            ans+=lst.bisect_left(num) #注意这里用bisect_left，如果bisect_right，就把0和1数量相同的子数组也统计了\n",
    "            lst.add(num)\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        #把0改成-1,把问题转化成求子数组和大于0的个数\n",
    "        pre=[0]\n",
    "        for v in nums:\n",
    "            if not v:\n",
    "                v-=1\n",
    "            pre.append(pre[-1]+v)\n",
    "        check=SortedList()\n",
    "        ans=0\n",
    "        for num in pre:\n",
    "            #这个优化要牢记,巨大优化,二分查找将目标列表放出来,作为方法而不是函数.\n",
    "            ans=(ans+check.bisect_left(num))%MOD\n",
    "            check.add(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        pref = [0]\n",
    "        for num in nums:\n",
    "            if num:\n",
    "                pref.append(1)\n",
    "            else:\n",
    "                pref.append(-1)\n",
    "            pref[-1] += pref[-2]\n",
    "        \n",
    "        ans = 0\n",
    "        lst = SortedList()\n",
    "        for num in pref:\n",
    "            ans += lst.bisect_left(num)\n",
    "            lst.add(num)\n",
    "        return ans % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        #把0改成-1,把问题转化成求子数组和大于0的个数\n",
    "        pre=[0]\n",
    "        for v in nums:\n",
    "            if not v:\n",
    "                v-=1\n",
    "            pre.append(pre[-1]+v)\n",
    "        check=SortedList()\n",
    "        ans=0\n",
    "        for num in pre:\n",
    "            #巨大优化,二分查找将目标列表放出来,作为方法而不是函数.\n",
    "            ans+=check.bisect_left(num)\n",
    "            check.add(num)\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        pref = [0]\n",
    "\n",
    "        for num in nums:\n",
    "\n",
    "            if num:\n",
    "\n",
    "                pref.append(1)\n",
    "\n",
    "            else:\n",
    "\n",
    "                pref.append(-1)\n",
    "\n",
    "            pref[-1]+=pref[-2]\n",
    "\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        lst = SortedList()\n",
    "\n",
    "        for num in pref:\n",
    "\n",
    "            ans+=lst.bisect_left(num) #注意这里用bisect_left，如果bisect_right，就把0和1数量相同的子数组也统计了\n",
    "\n",
    "            lst.add(num)\n",
    "\n",
    "        return ans%(10**9+7)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        sl = SortedList()\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        sl.add(2 * acc[0])\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            tmp = 2 * acc[i] - i\n",
    "            ans += sl.bisect_left(tmp)\n",
    "            sl.add(tmp)\n",
    "        return ans % mod \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9) + 7\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        # 前缀和的个数\n",
    "        cnts = Counter()\n",
    "        cnts[0] = 1\n",
    "        # cnt 维护所有满足条件的子数组个数（因为每次只有+1和-1的变化，所以每次只看边界波动值即可）\n",
    "        ans = cnt = s = 0\n",
    "        for num in nums:\n",
    "            if num:\n",
    "                # 前缀和为s的个数，当前和将要加一，所以所有和为s的前缀个数均可和当前值构成一个答案子数组\n",
    "                cnt += cnts[s]\n",
    "                s += 1\n",
    "            else:\n",
    "                # 前缀和为s + 1的个数，当前和将要减一，所以所有和为s + 1的前缀个数均不再能构成一个答案子数组\n",
    "                s -= 1\n",
    "                cnt -= cnts[s]\n",
    "            cnts[s] += 1\n",
    "            ans = (ans + cnt) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        MOD = int(1e9) + 7\n",
    "        cnts = Counter()\n",
    "        cnts[0] = 1\n",
    "        ans = cnt = s = 0\n",
    "        for x in nums:\n",
    "            if x > 0:\n",
    "                cnt += cnts[s]\n",
    "                s += 1\n",
    "            else:\n",
    "                cnt -= cnts[s - 1] # 4, 3, cnts[4] cnts[3]\n",
    "                s -= 1\n",
    "            cnts[s] += 1\n",
    "            ans = (ans + cnt) % MOD\n",
    "                # less than s, cnt\n",
    "                # less than s -1, \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        # 前缀和的个数\n",
    "        cnts = Counter()\n",
    "        cnts[0] = 1\n",
    "        # cnt 维护所有满足条件的子数组个数（因为每次只有+1和-1的变化，所以每次只看边界波动值即可）\n",
    "        ans = cnt = s = 0\n",
    "        for num in nums:\n",
    "            if num:\n",
    "                # 前缀和为s的个数，当前和将要加一，所以所有和为s的前缀个数均可和当前值构成一个答案子数组\n",
    "                cnt += cnts[s]\n",
    "                s += 1\n",
    "            else:\n",
    "                # 前缀和为s + 1的个数，当前和将要减一，所以所有和为s + 1的前缀个数均不再能构成一个答案子数组\n",
    "                s -= 1\n",
    "                cnt -= cnts[s]\n",
    "            cnts[s] += 1\n",
    "            ans = (ans + cnt) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        cnts=defaultdict(int)\n",
    "        cnts[0]=1\n",
    "        ans,cnt,pre=0,0,0\n",
    "        for v in nums:\n",
    "            if v:\n",
    "                #前缀和+1\n",
    "                cnt+=cnts[pre]\n",
    "                pre+=1\n",
    "            else:\n",
    "                #前缀和-1\n",
    "                pre-=1\n",
    "                cnt-=cnts[pre]\n",
    "            #每次遍历都需要添加当前前缀和到哈希表中\n",
    "            cnts[pre]+=1\n",
    "            ans=(ans+cnt)%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:\n",
    "        # 前缀和的个数\n",
    "        cnts = Counter()\n",
    "        cnts[0] = 1\n",
    "        # cnt 维护所有满足条件的子数组个数（因为每次只有+1和-1的变化，所以每次只看边界波动值即可）\n",
    "        ans = cnt = s = 0\n",
    "        for num in nums:\n",
    "            if num:\n",
    "                # 前缀和为s的个数，当前和将要加一，所以所有和为s的前缀个数均可和当前值构成一个答案子数组\n",
    "                cnt += cnts[s]\n",
    "                s += 1\n",
    "            else:\n",
    "                # 前缀和为s + 1的个数，当前和将要减一，所以所有和为s + 1的前缀个数均不再能构成一个答案子数组\n",
    "                s -= 1\n",
    "                cnt -= cnts[s]\n",
    "            cnts[s] += 1\n",
    "            ans = (ans + cnt) % MOD\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
